package 剑指offer.贪心与动态规划;

/**
 * 类似于 LeetCode 的 62、63题
 */
public class 第47题礼物的最大价值 {
    /*
    输入如下这么一个 array 数组
    从左上角出发一次只能往下或往右走一格，求所有路径中和最大的那个
     */
    public static void main(String[] args) {
        int[][] array = {
                {1, 10, 3, 8},
                {12, 2, 9, 6},
                {5, 7, 4, 11},
                {3, 7, 16, 5}
        }; // 最大路径：1、12、5、7、7、16、5
        System.out.println(maxValue(array));
        System.out.println(getMaxValue(array));
    }

    /*
    贪心策略：
    既然只能往下、往右走的话。我就每次走之前比一下，找和最大的方向，一直走

    本题不能使用贪心算法！！
     */
    public static int maxValue(int array[][]) {
        int ans = 0;
        if (array == null || array.length == 0) {
            return ans;
        }
        int rows = array.length;
        int cols = array[0].length;
        int i = 0;
        int j = 0;
        int currentMax = array[i][j];
        for (int n = 0; n < rows + cols - 1; n++) {
            if (i >= 0 && i + 1 <= rows - 1
                    && j >= 0 && j + 1 <= cols - 1) {
                int right = array[i][j + 1];
                int down = array[i + 1][j];
                int tmpMax1 = right + currentMax;
                int tmpMax2 = down + currentMax;
                // 往右边走的值更大
                if (tmpMax1 >= tmpMax2) {
                    currentMax = tmpMax1;
                    j++;
                } else {
                    currentMax = tmpMax2;
                    i++;
                }
            } else {
                if (j == cols - 1 && i != rows - 1) {
                    while (i <= rows - 1) {
                        currentMax += array[i++][j];
                    }
                } else {
                    while (j + 1 <= cols - 1) {
                        j++;
                        currentMax += array[i][j];
                    }
                }
            }
        }
        return ans = currentMax;
    }

    /**
     * 只能使用动态规划 ！
     * dp[i][j] 表示在 i、j 位置的最大价值
     * 因为只能往下或者往右移动，所以得到 dp[i][j] 最大值的前提是
     * 在 dp[i-1][j] 和 dp[i+1][j] 中已经有一个最大价值的数据了，
     * 然后用上面的最大价值加上自己，就是最终的最大价值！
     * <p>
     * 由此可见必须使用动态规划
     * <p>
     * 因此状态转移方程就是：
     * dp[i][j] = Max(dp[i-1][j],dp[i+1][j]) + value[i][j]
     * 它的含义就是：
     * 要想得到 dp[i][j] 的最大价值，先得到它上面或者左边的最大价值，然后加上自己即可
     */
    public static int getMaxValue(int[][] array) {
        if (array.length == 0 || array == null)
            return 0;
        int rows = array.length;
        int cols = array[0].length;
        // 创建状态转移方程
        int[][] dp = new int[rows][cols];
        // 开始循环处理每一个元素，而不是挑着选取
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 先求左边和上边元素的值，注意越界问题！
                int left = 0;
                int up = 0;
                if (i > 0)
                    up = dp[i - 1][j];
                if (j > 0)
                    left = dp[i][j - 1];
                dp[i][j] = Math.max(left, up) + array[i][j];
            }
        }
        return dp[rows - 1][cols - 1];
    }
}
